﻿Imports System.Collections.Generic

' Neighbour finding optimized by creating 2D grid cell buckets and only comparing nodes in one cell bucket against same/nerighbour cell buckets
' Much better speed than full many-to-many which would be O(N^2)

Friend Class cNeighbourNodeFinderGrid
    Implements INeighbourNodeFinder

    Private Structure sRectangle
        Dim MinimumX As Double
        Dim MinimumY As Double
        Dim MaximumX As Double
        Dim MaximumY As Double
    End Structure

    Private Structure sGridCellLocation
        Dim ColumnIndex As Integer
        Dim RowIndex As Integer
    End Structure

    Private mBoundingRectangle As sRectangle
    Private mNodeListArray(,) As List(Of cFirePerimeterPathNode)
    Private mArrayCellXSize As Double
    Private mArrayCellYSize As Double
    Private mColumnCount As Integer
    Private mRowCount As Integer


    Friend Function MakeListOfNodesWithCloseNeighbours(ByVal FirePerimeterPath As FirePerimeterPath, ByVal NumberOfNodesInPath As Integer, ByVal InsertNodeThresholdDistanceMetres As Double, ByVal CrossSearchProximityThresholdDistanceMetres As Double) As List(Of cFirePerimeterPathNode) Implements INeighbourNodeFinder.MakeListOfNodesWithCloseNeighbours

        Dim NodesWithCloseNeighbours As List(Of cFirePerimeterPathNode)
        Dim CurrentNode As cFirePerimeterPathNode
        Dim ComparingNode As cFirePerimeterPathNode
        Dim NeighbourNodes As List(Of cFirePerimeterPathNode)

        Me.InitializeGrid(FirePerimeterPath, NumberOfNodesInPath, CrossSearchProximityThresholdDistanceMetres)
        NodesWithCloseNeighbours = New List(Of cFirePerimeterPathNode)

        CurrentNode = FirePerimeterPath.FirstNode
        Do
            If CurrentNode.CutOperationStatus = cCutOperationTarget.eCutOperationStatus.ecosUntested Then
                CurrentNode.CutOperationStatus = cCutOperationTarget.eCutOperationStatus.ecosHasNoNeighbours
                NeighbourNodes = Me.ReturnNeighbours(CurrentNode)
                If Not NeighbourNodes Is Nothing Then
                    For Each ComparingNode In NeighbourNodes
                        If Not CurrentNode.IsNeighbour(ComparingNode) Then
                            If CurrentNode.IsDistanceToAnotherNodeLessThan(ComparingNode, CrossSearchProximityThresholdDistanceMetres) Then
                                CurrentNode.CutOperationStatus = cCutOperationTarget.eCutOperationStatus.ecosHasNearbyNeighbours
                                ComparingNode.CutOperationStatus = cCutOperationTarget.eCutOperationStatus.ecosHasNearbyNeighbours
                                NodesWithCloseNeighbours.Add(CurrentNode)
                                Exit For
                            End If
                        End If
                    Next
                End If
            End If
            CurrentNode = CurrentNode.NextNodeInPath
        Loop Until CurrentNode Is FirePerimeterPath.FirstNode

        Return NodesWithCloseNeighbours

    End Function


    Private Sub InitializeGrid(ByVal Path As FirePerimeterPath, ByVal NumberOfNodesInPath As Integer, ByVal CrossSearchProximityThresholdDistanceMetres As Double)

        Dim MaximumArrayCountInOneDimension As Integer = 20 ' max 1000x1000 array

        Dim CurrentNode As cFirePerimeterPathNode
        Dim NodeList As List(Of cFirePerimeterPathNode)
        Dim GridCellLocation As sGridCellLocation

        mBoundingRectangle = FindPathExtent(Path.FirstNode)
        With mBoundingRectangle
            mArrayCellXSize = (.MaximumX - .MinimumX) / MaximumArrayCountInOneDimension
            If mArrayCellXSize < CrossSearchProximityThresholdDistanceMetres Then
                mArrayCellXSize = CrossSearchProximityThresholdDistanceMetres
                mColumnCount = CType(Math.Ceiling((.MaximumX - .MinimumX) / mArrayCellXSize), Integer)
            Else
                mColumnCount = MaximumArrayCountInOneDimension
            End If
            mArrayCellYSize = (.MaximumY - .MinimumY) / MaximumArrayCountInOneDimension
            If mArrayCellYSize < CrossSearchProximityThresholdDistanceMetres Then
                mArrayCellYSize = CrossSearchProximityThresholdDistanceMetres
                mRowCount = CType(Math.Ceiling((.MaximumY - .MinimumY) / mArrayCellYSize), Integer)
            Else
                mRowCount = MaximumArrayCountInOneDimension
            End If
        End With

        'Create the array itself
        ReDim mNodeListArray(mColumnCount + 1, mRowCount + 1)

        'Store nodes to the array
        CurrentNode = Path.FirstNode
        Do
            GridCellLocation = GetGridCellForNode(CurrentNode)
            With GridCellLocation
                NodeList = mNodeListArray(.ColumnIndex, .RowIndex)
                If NodeList Is Nothing Then
                    NodeList = New List(Of cFirePerimeterPathNode)
                    mNodeListArray(.ColumnIndex, .RowIndex) = NodeList
                End If
            End With
            NodeList.Add(CurrentNode)
            CurrentNode = CurrentNode.NextNodeInPath
        Loop Until CurrentNode Is Path.FirstNode

    End Sub

    Private Function ReturnNeighbours(ByVal SeekingNode As cFirePerimeterPathNode) As List(Of cFirePerimeterPathNode)

        Dim ReturnList As List(Of cFirePerimeterPathNode)
        Dim SeekingNodeCellLocation As sGridCellLocation
        Dim ColumnIndex As Integer
        Dim RowIndex As Integer
        Dim NodeList As List(Of cFirePerimeterPathNode)
        Dim ComparingNode As cFirePerimeterPathNode

        SeekingNodeCellLocation = GetGridCellForNode(SeekingNode)

        ReturnList = New List(Of cFirePerimeterPathNode)
        For ColumnIndex = SeekingNodeCellLocation.ColumnIndex - 1 To SeekingNodeCellLocation.ColumnIndex + 1
            For RowIndex = SeekingNodeCellLocation.RowIndex - 1 To SeekingNodeCellLocation.RowIndex + 1
                NodeList = mNodeListArray(ColumnIndex, RowIndex)
                If Not NodeList Is Nothing Then
                    For Each ComparingNode In NodeList
                        If Not ComparingNode Is SeekingNode Then
                            ReturnList.Add(ComparingNode)
                        End If
                    Next
                End If
            Next
        Next

        Return ReturnList

    End Function

    Private Function GetGridCellForNode(ByVal Node As cFirePerimeterPathNode) As sGridCellLocation

        Dim WorkerDouble As Double
        Dim FlooredDouble As Double
        Dim WorkerInt As Integer
        Dim CellLocation As sGridCellLocation

        With mBoundingRectangle
            WorkerDouble = Node.MetricLocationX 'Metric location
            WorkerDouble = WorkerDouble - .MinimumX 'Metric offset vs min
            WorkerDouble = WorkerDouble / mArrayCellXSize 'divide by grid resolution (0-n)
            FlooredDouble = Math.Floor(WorkerDouble)
            WorkerInt = CType(FlooredDouble, Integer)
            If WorkerInt < mColumnCount Then
                WorkerInt = WorkerInt + 1
            End If
            CellLocation.ColumnIndex = WorkerInt

            WorkerDouble = Node.MetricLocationY 'Metric location
            WorkerDouble = WorkerDouble - .MinimumY 'Metric offset vs min
            WorkerDouble = WorkerDouble / mArrayCellYSize 'divide by grid resolution (0-n)
            FlooredDouble = Math.Floor(WorkerDouble)
            WorkerInt = CType(FlooredDouble, Integer)
            If WorkerInt < mRowCount Then
                WorkerInt = WorkerInt + 1
            End If
            CellLocation.RowIndex = WorkerInt

        End With

        Return CellLocation

    End Function

    Private Function FindPathExtent(ByVal FirstNodeInPath As cFirePerimeterPathNode) As sRectangle

        Dim CurrentNode As cFirePerimeterPathNode
        Dim Rectangle As sRectangle

        With Rectangle
            .MinimumX = Double.PositiveInfinity
            .MinimumY = Double.PositiveInfinity
            .MaximumX = Double.NegativeInfinity
            .MaximumY = Double.NegativeInfinity
        End With

        CurrentNode = FirstNodeInPath
        With Rectangle
            Do
                .MinimumX = Math.Min(.MinimumX, CurrentNode.MetricLocationX)
                .MinimumY = Math.Min(.MinimumY, CurrentNode.MetricLocationY)
                .MaximumX = Math.Max(.MaximumX, CurrentNode.MetricLocationX)
                .MaximumY = Math.Max(.MaximumY, CurrentNode.MetricLocationY)
                CurrentNode = CurrentNode.NextNodeInPath
            Loop Until CurrentNode Is FirstNodeInPath
        End With

        Return Rectangle

    End Function

End Class
